package 左哥算法.ch14单调栈;

import org.junit.Test;

import java.util.Stack;

public class 栈相关题目 {
    /**
     * ch01（非单调栈）：给你一个栈，请你在有限空间内将该栈数据放入另外一个栈中，并保证另一个栈是降序
     */
    @Test
    public void ch01(){
        Stack<Integer> stack = new Stack<>();
        stack.push(5);
        stack.push(6);
        stack.push(3);
        stack.push(2);
        stack.push(4);
        Stack<Integer> res = sortStack(stack);
        while (!res.empty()) {
            System.out.println(res.pop());
        }
    }
    public Stack<Integer> sortStack(Stack<Integer> stack){
        Stack<Integer> res = new Stack<>();
        int curr;
        while(!stack.empty()){
            curr = stack.pop();
            while (!res.empty()&&res.peek()>curr){  //将所有比curr大的数放入stack中
                stack.push(res.pop());
            }
            res.push(curr); //此时curr一定比res的栈顶要大，将curr放入res
        }
        return res;
    }
}
